[POJ 2217] Secretary

原题链接：http://poj.org/problem?id=2217
题目大意：给定两个字符串$S$和$T$。计算两个字符串的最长公共子串的长度。
数据范围：
多组测试数据
$1 \leq |S|,|T| \leq 10000$

样例输入：

2
Tady nejsou zadni mimozemstani.
Lide tady take nejsou.
Ja do lesa nepojedu.
V sobotu pojedeme na vylet.

样例输出

Nejdelsi spolecny retezec ma delku 7.
Nejdelsi spolecny retezec ma delku 5.

最长公共字串是连续的串，这跟$LCS$是不同的，因为$LCS$是可以不连续的。
字符串的题往往有固定套路可寻，这个题的套路就是可以把两个串拼到一起，再考虑一个串的情况应该怎么求。假设说我们把$S$和$T$拼成A = S + '\0' +T的话，对于这个题来说，实际上就是要求在$A$里的两个子串，使得他们相等，并且一个来自前半的$S$，一个来自后半的$T$。
先解决第一问：怎么求两个最长的相等子串的长度：这显然就是$LCP$的定义，在$SA$里，由于是按字典序排序的，所以两个距离越远的串显然前缀差异就越大，最接近的一定是相邻的，也就是说答案的长度就是$LCP$的最大值。
其次是第二问：怎么确定来源，这可以很自然的想到$SA$值的定义，因为后缀是一个起始位置到末尾，所以这个起始位置具体是在$n$之前还是之后就可以判断是来自哪边了。
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 3e6+7;
int lcp[N],sa[N];
namespace SA
{
	int rank[N],tmp[N];
	int n,k;
	bool sa_cmp(int i,int j)
	{
		if(rank[i] != rank[j])	return rank[i] < rank[j];
		else
		{
			int ri = i + k <= n ? rank[i + k] : -1;
			int rj = j + k <= n ? rank[j + k] : -1;
			return ri < rj;
		}
	}
	void build_sa(string& s)
	{
		n = s.size();
		for(int i = 0;i <= n;++i)
		{
			sa[i] = i;
			rank[i] = i < n ? s[i] : -1;
		}
		for(k = 1;k <= n;k *= 2)
		{
			sort(sa,sa + 1 + n,sa_cmp);
			tmp[sa[0]] = 0;
			for(int i = 1;i <= n;++i)	tmp[sa[i]] = tmp[sa[i - 1]] + sa_cmp(sa[i - 1],sa[i]);
			for(int i = 0;i <= n;++i)	rank[i] = tmp[i];
		}
	}
	bool contain(string& s,string& T)
	{
		int l = 0,r = s.size();
		while(l < r)
		{
			int mid = l + r >> 1;
			if(s.compare(sa[mid],T.size(),T) < 0)	l = mid + 1;
			else r = mid;
		}
		return s.compare(sa[l],T.size(),T) == 0;
	}
	void build_lcp(string& s)
	{
		n = s.size();
		for(int i = 0;i <= n;++i)	rank[sa[i]] = i;
		
		int h = 0;
		lcp[0] = 0;
		for(int i = 0;i < n;++i)
		{
			int j = sa[rank[i] - 1];
			if(h > 0)	--h;
			for(;j + h < n && i + h < n;++h)
				if(s[j + h] != s[i + h])	
					break;
			lcp[rank[i] - 1] = h;
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int T;cin >> T;cin.get();
	while(T--)
	{
		string s,t;getline(cin,s);getline(cin,t);
		// cout << s << endl;
		// cout << t << endl;
		int n = s.size();
		// cout << n << endl;
		s += '\0' + t;
		SA::build_sa(s);
		SA::build_lcp(s);
		int res = 0,m = s.size();
		// cout << m << endl;
		for(int i = 0;i < m;++i)
			if((sa[i] < n) != (sa[i + 1] < n))
				res = max(res,lcp[i]);
		printf("Nejdelsi spolecny retezec ma delku %d.\n",res);
	}
    return 0;